4.16 The purpose of this problem is to set an upper bound on the number of iterations of the Euclidean algorithm. a. Suppose that m = qn + r with q > 0 and 0<=r <= n. Show that m/2 > r. b. Let Ai be the value of A in the Euclidean algorithm after the ith iteration. Show that
c. Show that if m, n, and N are integers with (1 . m, n, . 2N), then the Euclidean algorithm takes at most 2N steps to find gcd(m, n).